package main

import "fmt"

func main() {
	fmt.Println(longestValidParentheses("())()((())"))
}

func longestValidParentheses(s string) int {
	opt := make([]int, len(s))
	max := 0
	size := len(s)
	for i := 1; i < size; i++ {
		if s[i] == ')' {
			if s[i-1] == '(' {
				if i >= 2 {
					opt[i] = opt[i-2] + 2
				} else {
					opt[i] = 2
				}
			} else if i-opt[i-1] > 0 && s[i-1-opt[i-1]] == '(' {
				if i-opt[i-1] >= 2 {
					opt[i] = opt[i-1] + opt[i-opt[i-1]-2] + 2
				} else {
					opt[i] = opt[i-1] + 2
				}
			}
			if opt[i] > max {
				max = opt[i]
			}
		}
	}
	fmt.Println(opt)
	return max
}
